The use of Global Navigation Satellite Systems (GNSS), such as GPS, for positioning vehicles is currently very widespread. A user is able to determine his or her position and a temporal reference by means of receiving and processing the signal of several satellites. This information is determined by knowing the position of the satellites and the time that the signal has taken to reach the user. It is further necessary to estimate the delays affecting the arrival time of the signal, such as deviations of the satellites, atmospheric delay and local effects and effects of the receptor. A user can currently determine his or her position with a precision of approximately a few meters in environments with good visibility, greater errors existing in non-controlled environments.
In addition to the position and time solution, there are techniques assuring a confidence level, or integrity, for said solution. Said techniques provide a geometric place (ellipsoid in space, ellipse in the plane) where it is assured that the user is located with an associated probability (for example 99.99999% in the aeronautic environment). Said techniques are already known and applied in SBAS systems, such as WAAS or EGNOS, or are calculated by means of autonomous RAIM (Receiver Autonomous Integrity Monitoring) algorithms or derivatives, both for critical safety applications and for those applications having legal or contractual implications. There are techniques providing integrity in low visibility or non-controlled environments, such as urban areas, as described in EP1729145, “Method and System for providing GNSS navigation position solution with guaranteed integrity in non-controlled environments”.
In addition the combined use of GNSS positioning and Geographic Information Systems (GIS) is very common, i.e. digital cartographic maps modeling the environment, such that the position information of the user can be related with the real world for the purpose of providing en route guidance or any other type of information.
The combination of satellite navigation and GIS is usually carried out by means of Map Matching (MM) techniques in applications for land transport. Said techniques identify which is the segment or road (street, highway, expressway) on which the user will most probably circulate, as well as his or her position therealong. In the event that there are no errors in the GNSS position nor in the GIS information, the process would be immediate, since the position would coincide with a point in the specific road on which the user is circulating. However, the reality is quite different since there are phenomena causing errors in the GNSS position—errors relating to satellites, atmospheric delays, multipath or signal reflection, particularly important in urban environments—, which can cause errors of up to hundreds of meters, as well as errors in the process of creating digital maps, mainly due to the scale factor, transforming coordinates, translating from a curved surface to a planar surface (generalization), position reference (datum) and the digitalization process.
The MM methods existing in the state of the art cover from the simplest algorithms, in which the position to the nearest segment or road at that instant is approximated, to other much more complicated algorithms. One of the main references in MM algorithms is “An Introduction to Map Matching for Personal Navigation Assistants”, Bernstein D. Komhauser A., 1996, which describes the first approaches to using MM with a positioning system. The proposed methods are divided into geometric and topological methods. The former only take into account the geometry of the segments defining the GIS map, whereas the latter further take into account the way in which said segments are connected. More advanced methods have been subsequently developed in which the trajectory is compared over time with the possible trajectories on the map by means of pattern recognition, Kalman filters, or fuzzy logic for selecting the suitable road. However the precision of these methods is not assured, nor do they provide the user with a confidence value, or integrity, of the adopted solution, but rather they are focused on adjusting the position to a segment in the best possible manner in most cases.
The probabilistic MM method, described in “Vehicle Location and Navigation System” Zhao Y., 1997 and in “High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications” Quddus M., 2006, could be considered background to the present invention, since it generates an ellipse from the covariance matrix of the position and analyzes only those segments which are located within said ellipse as possible segments, ruling out those the orientation of which does not coincide with that of the movement of the vehicle. The use of this ellipse based on the covariance of the position is similar to the previously described concept of integrity. The probabilistic method however has some drawbacks:
for example not being based on the integrity of the position which the navigation system provides, but rather it uses the covariance matrix only for selecting the possible roads within an area having great probability, which is not enough to guarantee the integrity of the position;
or for example proposing to use the direction of the movement for ruling out segments, risking ruling out the correct road in the case of turning, lane change, or error in calculating the direction of the movement, whereby upon using non-integral methods for selecting the road, the initial integrity, if there was any, would lose validity.
In the past few years methods which have attempted to provide an integrity value to the MM solution have been developed and are described below. Nevertheless the concept of integrity used does not correspond to the concept rigorously used in this patent, which is based on the concepts introduced by civil aviation. In fact, in no case does it assure the probability that the identified segment is the correct one, which is essential for the concept of integrity.
“Integrity of map-matching algorithms” Quddus M., Ochieng W., Noland B., 2006 and “High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications” Quddus M., 2006 propose an integral MM algorithm based on a global integrity indicator (0-100) for solutions given by already existing (topological, probabilistic and fuzzy logic) methods. Said indicator is determined by means of combining the following three criteria:                Integrity based on the uncertainty associated to the position solution: a standard deviation (σ) is determined based on the uncertainties of the map (σmap) and of the GPS position (σn and σe) and it is multiplied by a coefficient K, calculated by means of empirical results and depending on the number of lanes of the road. This indicator gives a measurement of the uncertainty of the GPS position and of the map, but in no case an integrity guarantee in and of itself.        Integrity based on the ability to correctly identify the road: The angle forming the segment selected by the MM algorithm and the trajectory of the vehicle is calculated from GPS or GPS+inertial sensors, and the smaller the angle the more integral the solution is considered to be. However, in addition to the fact that this indicator does not provide any integrity guarantee in and of itself, it will give a false alarm in the event that the vehicle is turning or changing lanes, and the direction does not coincide with that of the segment, or it will not detect a failure if the wrong road coinciding with the direction of the movement is selected for any reason.        Integrity based on the ability to precisely determine the position of the vehicle: An uncertainty indicator (R3dms) based on the covariance of the GPS position plus the typical road width is subtracted from the distance between the GPS position and the position given by the MM algorithm. In the event that the result is positive, it is assumed that the probability of integrity is lower. This indicator does not provide a quantifiable integrity measurement, nor does it assure integrity in the event that the result is negative or close to zero.        
Once the confidence index or integrity (0-100) is determined by means of the previous criteria using a fuzzy logic algorithm, a limit value (70) is determined under which an alarm is generated for the user. Said limit is based on empirical results for the purpose of optimizing the performance of the algorithm in the experiment conducted.
Based on the foregoing, it is concluded that the integrity provided by this algorithm cannot be considered reliable in all fields since it is not quantifiable nor is it based on theoretical fundamentals, therefore it can not be extrapolated to other situations beyond the experiments conducted. Therefore it does not provide the confidence necessary for critical safety applications or applications having legal or contractual implications. In addition, the performance level obtained (98.2% in the best of cases) does not seem to be sufficient for critical applications and is well under the confidence index of the method proposed herein.
Syed S. and Cannon E. in “Linking vehicles and maps to support location-based services” 2005; GPS World describe a novel method combining GIS, GPS and DR (Dead Reckoning) information for the purpose of improving the precision and reliability of positioning in urban environments. Nevertheless, said method does not provide any integrity indicator.
“Improving integrity and reliability of map matching techniques” Yu M. et al, 2006 also proposes different detection failure techniques in selecting a road (mismatch), combining GPS, INS and MM, and by means of curve recognition. Although it improves the reliability of the algorithm, 31.8% of failures still go undetected according to the results of the experiment conducted, and furthermore the method does not define or calculate a confidence value for the obtained solutions, but rather it is reduced to improving the reliability of the current MM techniques.
“Tightly-coupled GIS data in GNSS fix computations with integrity testing” Fouquet C., Bonnifait Ph., 2007, proposes an MM method with GPS using a tight coupling strategy in which a set of candidate segments is determined for each GPS solution based on certain criteria, and they are evaluated separately by means of a method similar to RAIM. In the event that there are several final candidates, the candidate minimizing the position residual of the least-squares solution is selected. Despite said reliability checking, this method does not assure the confidence of the selected solution. In addition, it does not take into account the information from previous instants.
European patent application published with number EP-1526357-A1 describes a method for detecting the position of a vehicle in a navigation system by means of map matching using the classic technique of the orthogonal projection of the position in the nearest segment. As with the aforementioned background documents, it does not assure integrity.
European patent application EP-1492072-A also describes a map matching method and system consisting of map layer processing optimization. It relates to improving the determination of the road in time real and does not assure integrity.